package Leetcode第一期;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author : K k
 * @date : 17:01 2020/8/27
 */
public class 二叉树的层序遍历_102 {
    List<List<Integer>> lists=new ArrayList<>();
    //列表
    public List<List<Integer>> levelOrderA(TreeNode root) {
        if (root==null){
            return lists;
        }
        List<TreeNode> nodes=new ArrayList<>(); //模拟队列
        nodes.add(root);

        while (!nodes.isEmpty()){
            List<Integer> list=new ArrayList<>(); //各层次用数组来存
            int size=nodes.size();

            for (int i=0;i<size;i++){
                TreeNode remove = nodes.remove(0);
                list.add(remove.val);
                if (remove.left!=null){
                    nodes.add(remove.left);
                }
                if (remove.right!=null){
                    nodes.add(remove.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }

    //递归
    public void helper(TreeNode node,int level){
        if (lists.size()==level){
            lists.add(new ArrayList<Integer>());
        }
        lists.get(level).add(node.val);
        if (node.left!=null){
            helper(node.left,level+1);
        }
        if (node.right!=null){
            helper(node.right,level+1);
        }
    }

    public List<List<Integer>> levelOrder1(TreeNode root) {
        if (root==null){
            return lists;
        }
        helper(root,0);
        Collections.reverse(lists);
        return lists;
    }


}
